/**
 * Created by L.jp
 * Description:给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，
 * 则返回"-1"。
 * 目前给出的数据，仅仅会存在一个最长的公共子序列
 * User: 86189
 * Date: 2022-08-26
 * Time: 22:12
 */
public class Solution {
    public String LCS (String s1, String s2) {
        //使用字符串动态规划数组存储最长公共子序列
        int n=s1.length();
        int m=s2.length();
        String[][] dp=new String[n+1][m+1];
        //借助空字符串来构造初始化
        for(int i=0;i<=n;i++){
            //j==0时，表示s2为空串
            dp[i][0]="";
        }
        for(int i=0;i<=m;i++){
            //i==0时，s1为空串
            dp[0][i]="";
        }
        //构造数组
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+s1.charAt(i-1);
                }else {
                    dp[i][j]=dp[i][j-1].length()>dp[i-1][j].length() ? dp[i][j-1] : dp[i-1][j];
                }
            }
        }
        return dp[n][m]=="" ? "-1": dp[n][m];
    }
}
